package com.demo.alg.lru;

import java.util.HashMap;
import java.util.Map;

public class LRUCache2<K, V> {
    //容量
    private int capacity;
    //当前有多少节点的统计
    private int count;
    //缓存节点
    private Map<K, Node<K, V>> nodeMap;
    private Node<K, V> head;
    private Node<K, V> tail;

    public LRUCache2(int capacity) {
        if (capacity < 1) {
            throw new IllegalArgumentException(String.valueOf(capacity));
        }
        this.capacity = capacity;
        this.nodeMap = new HashMap<>();
        //初始化头节点和尾节点，利用哨兵模式减少判断头结点和尾节点为空的代码
        Node<K, V> headNode = new Node<>(null, null);
        Node<K, V> tailNode = new Node<>(null, null);
        headNode.next = tailNode;
        tailNode.pre = headNode;
        this.head = headNode;
        this.tail = tailNode;
    }

    public void put(K key, V value) {
        Node<K, V> node = nodeMap.get(key);
        if (node == null) {
            if (count >= capacity) {
                //先移除一个节点
                removeNode();
            }
            node = new Node<>(key, value);
            //添加节点
            addNode(node);
        } else {
            //移动节点到头节点
            moveNodeToHead(node);
        }
    }

    public Node<K, V> get(K key) {
        Node<K, V> node = nodeMap.get(key);
        if (node != null) {
            moveNodeToHead(node);
        }
        return node;
    }

    private void removeNode() {
        Node<K, V> node = tail.pre;
        //从链表里面移除
        removeFromList(node);
        nodeMap.remove(node.key);
        count--;
    }

    private void removeFromList(Node<K, V> node) {
        Node<K, V> pre = node.pre;
        Node<K, V> next = node.next;

        pre.next = next;
        next.pre = pre;

        node.next = null;
        node.pre = null;
    }

    private void addNode(Node<K, V> node) {
        //添加节点到头部
        addToHead(node);
        nodeMap.put(node.key, node);
        count++;
    }

    private void addToHead(Node<K, V> node) {
        Node<K, V> next = head.next;
        next.pre = node;
        node.next = next;
        node.pre = head;
        head.next = node;
    }

    public void moveNodeToHead(Node<K, V> node) {
        //从链表里面移除
        removeFromList(node);
        //添加节点到头部
        addToHead(node);
    }

    class Node<k, v> {
        k key;
        v value;
        Node<k, v> pre;
        Node<k, v> next;

        public Node(k key, v value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public static void main(String[] args) {
    	LRUCache2<Integer, Integer> cache = new LRUCache2<>(5);
    	cache.put(1, 1);
    	cache.put(2, 2);
    	cache.put(3, 3);
    	cache.put(4, 4);
    	cache.put(5, 5);
    	cache.put(6, 6);
    	cache.put(7, 7);
    	cache.put(6, 6);
    	cache.put(4, 4);
    	cache.put(0, 0);
    	System.out.println(cache);
	}
    
}